#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//vector<vector<int>> ret;
//vector<int> path;
//int n;
//void dfs(vector<vector<int>>& graph,int i)
//{
//	if (i == n - 1)
//	{
//		ret.push_back(path);
//		return;
//	}
//	for (auto& e : graph[i])
//	{
//		path.push_back(e);
//		dfs(graph, e);
//		path.pop_back();
//	}
//}
//
//vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//	n = graph.size();
//	path.push_back(0);
//	dfs(graph, 0);
//	return ret;
//}
bool bfs(vector<vector<int>>& rooms)
{
	int n = rooms.size();
	queue<int> q;
	vector<bool> visited(n,false);
	q.push(0);
	while (!q.empty())
	{
		auto tmp = q.front();
		q.pop();
		visited[tmp] = true;
		for (auto& e : rooms[tmp])
		{
			if (visited[e] == false)
				q.push(e);
		}
	}
	for (int i = 0; i < n; i++)
		if (visited[i] == false)
			return false;
	return true;
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
	return bfs(rooms);
}
vector<bool> visited;
long long dfs(int i, vector<vector<int>>& graph)
{
	visited[i] = true;
	long long ret = 1;
	for (auto& e : graph[i])
	{
		if (visited[e] == false)
		{
			ret+=dfs(e, graph);
		}
	}
	return ret;
}
long long countPairs(int n, vector<vector<int>>& edges) {
	vector<vector<int>> graph(n);
	for (auto& v : edges)
	{
		graph[v[0]].push_back(v[1]);
		graph[v[1]].push_back(v[0]);
	}
	visited.resize(n, false);
	long long ret = 0;
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == false)
		{
			long long cnt = dfs(i,graph);
			ret += cnt * (n - cnt);
		}
	}
	return ret / 2;
}
int main()
{

	return 0;
}